package ZhangHeng.com.leetcode69;

class Solution0 {
    public int mySqrt(int x) {
        for(long i=0;i<x;i++){
            if(i*i<=x&&(i+1)*(i+1)>x){
                return (int)i;
            }
        }
        return x;
    }
}


class Solution1 {
    public int mySqrt(int x) {
        int l = 0;
        int r = x /2;

        if(x==1) return 1;
        if(x==0) return 0;

        while(l < r){
            int mid = (l + r + 1) / 2;

            if(mid*mid > x) r = mid - 1;//mid * mid 可能会越界

            else l = mid;
        }
        return l;
    }
}


class Solution {
    public int mySqrt(int x) {
        int l = 0;
        int r = x;

        while(l < r){
            int mid = (l + r ) / 2 + 1; //+是为了避免死循环的
            if((long) mid*mid > x) r = mid - 1;

            else if((long) mid*mid < x) l = mid;
            else return mid ;
        }
        return l;
    }
}

public class test {

}
